package dipl.algorithm.math.fp.geometry.op;

import dipl.algorithm.math.fp.geometry.Bridge2d;
import dipl.algorithm.math.fp.geometry.ConvexHull2d;
import dipl.algorithm.math.fp.primitive.Interval1df;
import dipl.algorithm.math.fp.primitive.Point2df;
import dipl.algorithm.math.fp.primitive.Vector2df;
import dipl.algorithm.math.fp.primitive.op.Point2dOps;
import dipl.algorithm.math.fp.primitive.op.Vector2dOps;
import dipl.algorithm.math.primitive.Tuple2;
import dipl.algorithm.math.primitive.Side;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Stack;

/**
 * Class provides methods on convex polygons
 */
public class ConvexPolygons2d {

	//
	// PUBLIC METHODS
	//
	
	/**
	 * Calculates and returns bridges between an n-sided and m-sided convex polygon.
	 * The polygon points are assumed to be ordered clockwise.
	 * The returned bridges are ordered clockwise around the minimal convex polygon containing both
	 * given polygons. They are also aligned clockwise, so they can be traversed around both polygons.
	 * None of the bridges returned are collinear.
	 * If no bridge is returned then one of given polygons is contained in the other.
	 * The algorithm used here is based on the rotating calipers method and has a running time of O(N) where
	 * N = max(n,m).
	 *	Assumes that given parameters are not <code>null</code>
	 * @param p1
	 * @param p2
	 * @returns
	 */
	public static LinkedList<Bridge2d> CalculateBridges( Point2df[] p1, Point2df[] p2 ) {
		int n = p1.length; // input length
		int m = p2.length; // input length
		LinkedList<Bridge2d> bridges = new LinkedList<Bridge2d>(); // bridges found so far

		// degenerate case: one polygon is empty
		if( n == 0 || m == 0 )
			return bridges;

		// Degenerate case: both polygons are points.
		// The bridge is simply the line connecting theese points.
		if( p1.length == 1 && p2.length == 1 ) {
			if( p1[0].x != p2[0].x || p1[0].y != p2[0].y ) // if points are distinct -> bridge
				bridges.addLast( new Bridge2d( p1, 0, p2, 0 ) );
			return bridges;
		}

		// Degenerate case: first polygon is a point.
		// If the point is contained in second polygon then there is no bridge.
		// Otherwise there are two bridges.
		Tuple2<Integer,Integer> temp; // temporary
		if( p1.length == 1 ) {
			if( ConvexPolygons2d.IsPointProperlyContained( p2, p1[0] ) )
				return bridges;
			temp = Point2dSetOps.ComputeCone( p2, p1[0] );
			bridges.addLast( new Bridge2d( p1, 0, p2, temp.fst ) );
			bridges.addLast( new Bridge2d( p2, temp.snd, p1, 0 ) );
			return bridges;
		}
		// Degenerate case: second polygon is a point.
		// See former case.
		else if( p2.length == 1 ) {
			if( ConvexPolygons2d.IsPointProperlyContained( p1, p2[0] ) )
				return bridges;
			temp = Point2dSetOps.ComputeCone( p1, p2[0] );

			bridges.addLast( new Bridge2d( p2, 0, p1, temp.fst ) );
			bridges.addLast( new Bridge2d( p1, temp.snd, p2, 0 ) );
			return bridges;
		}

		// Find vertices i and j in both polygons with maximum y-coordinate
		// these vertices are the starting point for the algorithm
		int istart, jstart; // found indices
		int i, j, k; // indices
		double sgn; // signed temporary
		istart = 0;
		for( k = 1; k < n; k++ ) {
			sgn = p1[k].y-p1[istart].y;
			if( sgn > 0.0 || (sgn == 0.0 && p1[k].x >= p1[istart].x) ) {
				istart = k;
			}
			else break;
		}
		jstart = 0;
		for( k = 1; k < m; k++ ) {
			sgn = p2[k].y-p2[jstart].y;
			if( sgn > 0.0 || (sgn == 0.0 && p2[k].x >= p2[jstart].x) ) {
				jstart = k;
			}
			else break;
		}

		// Look for bridges.
		// Possible bridges are formed by co-podal pairs of vertices.
		// co-podal pairs are represented by their vertex indices.
		Side side, side1, side2, side3, side4; // side helper
		int i_n, j_m, ip1_n, jp1_m; // i,j modulo helpers
		Vector2df slDir_1 = new Vector2df(); // supporting line direction at poly1
		Vector2df slDir_2 = new Vector2df(); // supporting line direction at poly2
		Tuple2<Integer,Integer> cpp; // currently examined co-podal pair
		Stack<Tuple2<Integer,Integer>> coPodals = new Stack<Tuple2<Integer, Integer>>(); // cop-podal index pairs
		boolean left, right; // for one-side test of supporting line
		i = istart; j = jstart;
		while( i+j < (istart+n)+(jstart+m) ) { // loop until reached start configuration
		 // System.Console.Out.Write( "i:"+i.ToString()+","+"j:"+j.ToString()+" " );
			i_n = i%n; j_m = j%m;
			ip1_n = (i+1)%n; jp1_m = (j+1)%m;
			// rotate supporting line vector until it coincides with at least one edge
			slDir_1.Set( p1[ip1_n].x-p1[i_n].x, p1[ip1_n].y-p1[i_n].y );
			slDir_2.Set( p2[jp1_m].x-p2[j_m].x, p2[jp1_m].y-p2[j_m].y );
			side = Vector2dOps.WhichSide( slDir_2, slDir_1 );
			if( side == Side.Onto ) { // supporting line coincides with both edges -> three co-podal pairs
				coPodals.push( new Tuple2<Integer, Integer>( i_n, j_m ) );
				coPodals.push( new Tuple2<Integer, Integer>( ip1_n, j_m ) );
				coPodals.push( new Tuple2<Integer, Integer>( i_n, jp1_m ) );
				i++; j++;
			}
			else if( side == Side.Right ) { // second supporting line coincides first
				coPodals.push( new Tuple2<Integer, Integer>( i_n, j_m ) );
				j++;
			}
			else { // first supporting line coincides first
				coPodals.push( new Tuple2<Integer, Integer>( i_n, j_m ) );
				i++;
			}
			// test co-podal pairs found whether they define bridges
			Bridge2d b = null; // temporary holding created bridge
			while( coPodals.size() > 0 ) {
				cpp = coPodals.pop();
				left = false;
				right = false;
				side1 = Line2dOps.WhichSide( p1[CircleMod( cpp.fst-1, n )], p1[cpp.fst], p2[cpp.snd] );
				side2 = Line2dOps.WhichSide( p1[(cpp.fst+1)%n], p1[cpp.fst], p2[cpp.snd] );
				left |= side1 == Side.Left; right |= side1 == Side.Right;
				left |= side2 == Side.Left; right |= side2 == Side.Right;
				if( left && right ) continue;
				side3 = Line2dOps.WhichSide( p2[CircleMod( cpp.snd-1, m )], p1[cpp.fst], p2[cpp.snd] );
				side4 = Line2dOps.WhichSide( p2[(cpp.snd+1)%m], p1[cpp.fst], p2[cpp.snd] );
				left |= side3 == Side.Left; right |= side3 == Side.Right;
				left |= side4 == Side.Left; right |= side4 == Side.Right;
				if( left && right ) continue;
				if( Point2dOps.Collinear( p1[cpp.fst], p2[CircleMod( cpp.snd-1, m )], p2[cpp.snd] )  )
					continue;
				if( Point2dOps.Collinear( p2[cpp.snd], p1[CircleMod( cpp.fst, n )], p1[(cpp.fst+1)%n] ) )
					continue;
				if( bridges.size() == 0 ) {
					b = new Bridge2d( p1, cpp.fst, p2, cpp.snd );
					AlignBridgeClockwise( b );
				}
				else {
					// alternate bridge end-points
					if( bridges.getLast().poly1 == p1 ) {
						b = new Bridge2d( p2, cpp.snd, p1, cpp.fst );
					}
					else {
						b = new Bridge2d( p1, cpp.fst, p2, cpp.snd );
					}
				}
				bridges.addLast( b );
			}
		}
		return bridges;
	}

	/**
	 * This method determines whether or not given two convex polygons
	 * "cross".
	 * "Crossing" means that end-point indices in hull #1 and indices in hull #2
	 * stick out of the other hull alternating in clockwise order.
	 * It is assumed that given hulls intersect and vertices are given sorted lexicographically
	 * in clockwise order.
	 * It is also assumed that no vertices are collinear in each hull.
	 * @param h1
	 * @param h2
	 * @returns
	 */
	public static boolean Crossing( ConvexHull2d h1, ConvexHull2d h2 ) {

		// some temporaries for shorter code
		Point2df[] poly1 = h1.Vertices();
		Point2df[] poly2 = h2.Vertices();
		int p1_0 = h1.FirstPointsetIndex();
		int p1_n = h1.LastPointsetIndex();
		int p2_0 = h2.FirstPointsetIndex();
		int p2_m = h2.LastPointsetIndex();

		// First of all try to find exactly 4 bridges between polygons
		LinkedList<Bridge2d> bridgeList = CalculateBridges( poly1, poly2 );

		if( bridgeList.size() != 4 ) // four bridges are needed to cross
			return false;

		// build bridge array for faster access
		Bridge2d[] bridges = new Bridge2d[bridgeList.size()];
		int i = 0; // index
		for( Bridge2d bridge : bridgeList ) {
			bridges[i] = bridge;
			i++;
		}

		// from the four bridges calculate four polygonal chains
		int k,l; // indices
		int[] cs = new int[4], ce = new int[4]; // start and end of chains
		Bridge2d b = bridges[0]; // current bridge
		Point2df[] cp = b.poly2; // (current) polygon to which first polygonal chain belongs
		Tuple2<Integer, Integer> temp = StepDown( b.poly1, b.i, b.poly2, b.j );
		ce[3] = temp.fst;
		cs[0] = temp.snd;

		for( k = 1; k < 4; k++ ) {
			b = bridges[k];
			temp = StepDown( b.poly1, b.i, b.poly2, b.j );
			ce[k-1] = temp.fst;
			cs[k] = temp.snd;
		}

		// look for end-point indices on chains to see whether they stick out alternating
		boolean found_p1_0 = false; // first index on poly #1 was found?
		boolean found_p1_n = false; // last index on poly #1 was found?
		boolean found_p2_0 = false; // first index on poly #2 was found?
		boolean found_p2_m = false; // last index on poly #2 was found?
		boolean nextk = false; // continue?
		for( k = 0; k < 4; k++ ) {
			l = cs[k];
			nextk = false;
			do {
				if( cp == poly1 ) {
					if( l == p1_0 ) {
						found_p1_0 = true;
						nextk = true;
					}
					else if( l == p1_n ) {
						found_p1_n = true;
						nextk = true;
					}
				}
				else if( cp == poly2 ) {
					if( l == p2_0 ) {
						found_p2_0 = true;
						nextk = true;
					}
					else if( l == p2_m ) {
						found_p2_m = true;
						nextk = true;
					}
				}
				if( l != ce[k] )
					l=(l+1)%cp.length;
				else
					nextk = true;
			} while( nextk == false );
			cp = cp == poly1 ? poly2 : poly1; // alternate examined polygon
		}
		return (found_p1_0 && found_p1_n && found_p2_0 && found_p2_m);
	}

	/**
	 * Calculates anti-podal pairs of given n-sided convex polygon using the algorithm of Shamos.
	 * The polygon vertices are assumed to be given in clockwise order.
	 * Running time: O(n)
	 * @param poly polygon
	 * @return list of anti-podal pairs
	 */
	public static LinkedList<Tuple2<Point2df,Point2df>> CalculateAntipodalPairs( Point2df[] poly ) {
		int n = poly.length;
		LinkedList<Tuple2<Point2df, Point2df>> pairs = new LinkedList<Tuple2<Point2df, Point2df>>();
		// polygon is empty or one point or a line -> diameter is zero!
		if( n <= 1 )
			return pairs;

		int pi = n-1; //							index of point p
		Point2df p = poly[n-1]; //			p
		Point2df nextp = poly[0]; // successor of p
		int qi = 0; //							index of point q
		Point2df q = poly[1]; //			q
		Point2df nextq = poly[2%n]; // succesor of q
		// try to find point q farthest from p on polygon
		while( Point2dOps.Area( p, nextp, nextq ) < Point2dOps.Area( p, nextp, q ) ) {
			qi = (qi+1)%n;
			q = poly[qi];
			nextq = poly[(qi+1)%n];
		}
		Point2df q0 = q;				//		store last point traversed by q-chain
		Point2df p0 = poly[0];	//		store starting p
		int numPairs = 0;			//		counts  pairs found
		int maxPairs = 3*n>>1;	//	maximum possible number of pairs
		while( q != p0 ) {
			// emergency stop
			if( numPairs >= maxPairs )
				return pairs;
			pi = (pi+1)%n;
			p = poly[pi];
			nextp = poly[(pi+1)%n];
			pairs.addLast( new Tuple2<Point2df, Point2df>( p, q ) );
			numPairs++;
			while( Point2dOps.Area( p, nextp , nextq ) < Point2dOps.Area( p, nextp, q ) ) {
				qi = (qi+1)%n;
				q = poly[qi];
				nextq = poly[(qi+1)%n];
				if( p != q0 || q != p0 ) {
					pairs.addLast( new Tuple2<Point2df, Point2df>( p, q ) );
					numPairs++;
				}
				else
					return pairs;
			}
			if( Point2dOps.Area( p, nextp , nextq ) == Point2dOps.Area( p, nextp, q) ) {
				if( p != q0 || q != poly[n-1] )
					pairs.addLast( new Tuple2<Point2df, Point2df>( p, nextq ) );
				else
					pairs.addLast( new Tuple2<Point2df, Point2df>( nextp, q ) );
			}
		}
		return pairs;
	}

	/**
	 * Calculates diameter of given n-sided convex polygon using the algorithm of Shamos.
	 * The polygon vertices are assumed to be given in clockwise order.
	 * Running time: O(n)
	 * @param poly polygon
	 * @param squaredDiameter if {@code true} square of diameter is returned
	 * @return diameter or squared diameter
	 */
	public static double CalculateDiameter( Point2df[] poly, boolean squaredDiameter ) {
		int n = poly.length;
		// polygon is empty or a single point -> diameter is zero!
		if( n <= 1 )
			return 0.0;
		// 2 points -> diameter is distance between them
		if( n == 2 ) {
			double diameter = Point2dOps.SquareDistance( poly[0], poly[1] );
			return squaredDiameter ? diameter : Math.sqrt( diameter );
		}
		// get all anti-podal pairs (those pairs are candidates for having maximum distance)
		double diameter = 0.0;
		LinkedList<Tuple2<Point2df, Point2df>> pairs = CalculateAntipodalPairs( poly );
		if( pairs.size() == 0 )
			return diameter;
		// we have all anti-podal pairs -> get max of distance
		ListIterator<Tuple2<Point2df,Point2df>> iter = pairs.listIterator();
		while( iter.hasNext() ) {
			Tuple2<Point2df,Point2df> pair = iter.next();
			diameter = Math.max( Point2dOps.SquareDistance( pair.fst, pair.snd ), diameter );
		}
		if( squaredDiameter )
			return diameter;
		else
			return Math.sqrt( diameter );
	}

	/**
	 * Tests whether a n-sided convex polygon intersects (or touches) another m-sided convex polygon.
	 * The Algorithm uses the method of separting axes and has a running time of O(nm).
	 * It is assumed that the polygon vertices are ordered clockwise (which makes some
	 * optimizations possible)
	 * </summary>
	 * @param poly1 n-sided polygon
	 * @param poly2 m-sided polygon
	 * @returns intersects or not
	 */
	public static boolean Intersect( Point2df[] poly1, Point2df[] poly2 ) {

		int n = poly1.length;
		int m = poly2.length;
		int i, ip1; // indices

		Vector2df axis = new Vector2df(); // axis of projection;
		Vector2df linePP;

		// find axis for first polygon first
		linePP = Vector2dOps.DifferenceVector( poly1[0], poly2[0] ); // line from poly1 to poly2

		// take every pair of sides from both polygons and try to construct an axis of
		// separation from them
		for( i = 0; i < n; i++ ) {
			ip1 = (i+1)%n; // i+1
			// for optimization it is tested whether normal of i-th side points away from other polygon
			// and in that case proceed to the next side. This is possible, because the polygon
			// points are ordered clockwise so that their normals always point away from polygon

			// calculate "normal" of current side (not normalized)
			axis.Set( -(poly1[ip1].y-poly1[i].y), poly1[ip1].x-poly1[i].x );

			// normal points away from other polygon
			if( Vector2dOps.DotProduct( axis, linePP ) <= 0.0 )
				continue;

			// project polygon edges on calculated axis
			// if intervals do not intersect then there is an axis of separation
			// and hence both polygons do not intersect
			if( !IntervalsIntersect( axis, poly1, poly2 ) )
				return false;
		}

		// find axis for second polygon
		linePP = Vector2dOps.DifferenceVector( poly2[0], poly1[0] ); // line from poly2 to poly1

		for( i = 0; i < m; i++ ) {
			ip1 = (i+1)%m; // i+1
			// for optimization it is tested whether normal of i-th side points away from other polygon
			// and in that case proceed to the next side. This is possible, because the polygon
			// points are ordered clockwise so that their normals always point away from polygon

			// calc "normal" of current side (not normalized)
			axis.Set( -(poly2[ip1].y-poly2[i].y), poly2[ip1].x-poly2[i].x );

			if( Vector2dOps.DotProduct( axis, linePP ) <= 0.0 )
				continue;

			// if project intervals do not intersect then there is an axis of separation
			// and hence both polygons do not intersect
			if( !IntervalsIntersect( axis, poly2, poly1 ) )
				return false;
		}

		// no separating axis found
		return true;
	}

	/**
	 * Tests whether or not given point p is contained in given convex polygon.
	 * Method assumes given parameters to be not <code>null</code>
	 * Furthermore the polygon vertices are assumed to be distinct,
	 * ordered clockwise or counter-clockwise and no three
	 * vertices are collinear.
	 * Running-time: O(n)
	 * @param poly
	 * @param p
	 * @return
	 */
	public static boolean IsPointContained( Point2df[] poly, Point2df p ) {
		if( poly.length == 0 )
			return false;
		// degenerate case: polygon is a point
		if( poly.length == 1 )
			return (p.x == poly[0].x && p.y == poly[1].y);

		int i = 0; // indices
		int n = poly.length;
		// find first polygon side on which given point do not lie.
		Side side = Side.Onto;
		while( i < n && side == Side.Onto ) {
			side = Line2dOps.WhichSide( p, poly[i], poly[(i+1)%n] );
			i++;
		}
		// point lies on polygon side
		if( side == Side.Onto )
			return true;
		if( i == n )
			return false; // point lies outside of polygon (whose vertices must all be collinear in this case)
		Side temp;
		while( i < n ) {
			temp = Line2dOps.WhichSide( p, poly[i], poly[(i+1)%n] );
			if( temp != Side.Onto && side != temp )
				return false;
			i++;
		}
		return true;
	}

	/**
	 * Tests whether or not given point p is contained in the interior of given convex polygon.
	 * The polygon vertices are assumed to be distinct, ordered clockwise or counter-clockwise and no three
	 * vertices are collinear.
	 *
	 * Running-time: O(n)
	 * @param poly
	 * @param p
	 * @return
	 */
	public static boolean IsPointProperlyContained( Point2df[] poly, Point2df p ) {
		// degenerate case: polygon is a point or a line -> no polygon interior
		if( poly.length <= 2 )
			return false;

		int i; // indices
		int n = poly.length;
		// the point lies within the interior of the polygon if it lies always on the same of all polygon
		// edges directed
		Side side = Line2dOps.WhichSide( p, poly[0], poly[1] );
		for( i = 1; i < n; i++ ) {
			if( side != Line2dOps.WhichSide( p, poly[i], poly[(i+1)%n] ) )
				return false;
		}
		return true;
	}

	/**
	 * Calculates union of given convex polygons which itself is a convex polygon.
	 * The additional information contained in the hulls (first and last indices in their original point-sets together
	 * with the original point-set) is lost in the union.
	 * Running time: O(n)
	 * @param h1
	 * @param h2
	 */
	public static ConvexHull2d Union( ConvexHull2d h1, ConvexHull2d h2 ) {
		Point2df[] p1 = h1.Vertices(); // helpers
		Point2df[] p2 = h2.Vertices();
		// calc bridges between polygons
		LinkedList<Bridge2d> bridges = CalculateBridges( p1, p2 );
		ConvexHull2d union = new ConvexHull2d(); // resulting union
		// no bridges -> one of the polygons is properly contained in the other, return the outer one
		if( bridges.size() == 0 ) {
			if( IsPointContained( p1, p2[0] ) ) {
				union.SetVertices( p1 );
			}
			else {
				union.SetVertices( p2 );
			}
			return union;
		}

		// build bridge array for faster access and align bridges clockwise
		Bridge2d[] arr_bridges = new Bridge2d[bridges.size()];
		int i = 0; // index
		while( bridges.size() > 0 ) {
			arr_bridges[i] = bridges.removeFirst();
			i++;
		}

		LinkedList<Point2df> list_hull = ConstructHullFromBridges( arr_bridges );
		Point2df[] hull = new Point2df[list_hull.size()];
		i = 0;
		for( Point2df p : list_hull ) {

			hull[i] = p;
			i++;
		}
		union.SetVertices( hull );
		return union;
	}

	//
	// AUXILLIARY METHODS
	//
	
	/**
	 * Given a bridge( p1, i, p2, j ) this method aligns the bridge so that
	 * i+1 is clockwise from i around p1 and j+1 is counter-clockwise from j around p2.
	 * This alignment is needed in "CalculateBridges"-Method to align first bridge found
	 * @param b bridge
	 */
	private static void AlignBridgeClockwise( Bridge2d b ) {
		Point2df[] p1 = b.poly1;
		Point2df[] p2 = b.poly2;
		int n = b.poly1.length;
		int m = b.poly2.length;
		// look for correct side of indices
		boolean c = Line2dOps.WhichSide( p1[(b.i+1)%n], p1[b.i], p2[b.j] ) == Side.Right &&
					   	  Line2dOps.WhichSide( p2[CircleMod( b.j-1, m )], p2[b.j], p1[b.i] ) == Side.Left;
		// swap bridge if indices incorrect
		if( !c )
			b.Swap();
	}

	/**
	 * Appends a polygonal chain to given list. The chain is taken from given n-sided polygon p.
	 * It starts at s and ends at (e-1)%n. (assuming s != e)
	 * @param p
	 * @param s
	 * @param e
	 * @param list
	 */
	private static void AppendPolygonChain( Point2df[] p, int s, int e, /*out*/LinkedList<Point2df> list ) {
		int i = s;
		int n = p.length;
		do {
			list.addLast( p[i] );
			i = (i+1)%n;
		} while( i != e );
	}

	/**
	 * Returns:
	 * i%n       , if >= 0;
	 * n+(i%n)   , otherwise;
	 * @param i
	 * @param n
	 * @return
	 */
	public static int CircleMod( int i, int n ) {
		int res = i%n;
		return res < 0 ? n+res : res;
	}

	private static LinkedList<Point2df> ConstructHullFromBridges( Bridge2d[] arr ) {
		LinkedList<Point2df> res = new LinkedList<Point2df>(); // list will contain resulting hull points
		// walk along bridges and construct hull
		int n = arr.length;
		Bridge2d b = arr[0];
		// simple case:
		if( n == 1 && b.poly1.length == 1 && b.poly2.length == 1 ) {
			res.addLast( b.poly1[0] );
			res.addLast( b.poly2[0] );
			return res;
		}
		// 1 bridge but polygons are no points
		// -> complicated case. since there is one chain there must be three
		// collinear points somewhere in the chain. there the polygons "switch".
		if( n == 1 ) {
			
		}
		int istart = arr[0].i;
		Point2df[] pstart = arr[0].poly1;
		for( int i = 0; i < n; i++ ) {
			b = arr[i];
			res.addLast( b.poly1[b.i] );
			if( b.j != arr[(i+1)%n].i )
				AppendPolygonChain( b.poly2, b.j, arr[(i+1)%n].i, res );
			else if( b.poly2 != pstart || b.j != istart )
				res.addLast( b.poly2[b.j] );
		}
		return res;
	}

	/**
	 * Method is used in <code>intersect()</code>-method.
	 * It projects all polygon edges onto given axis and returns
	 * whether or not projection intervals intersect
	 * @param axis axis of porjection
	 * @param poly1
	 * @param poly2
	 * @return intersection or not
	 */
	private static boolean IntervalsIntersect( Vector2df axis, Point2df[] poly1, Point2df[] poly2 ) {
		int i; // indices
		int n = poly1.length;
		int m = poly2.length;
		double a; // temporary for interval calculation
		Interval1df int1 = new Interval1df();
		Interval1df int2 = new Interval1df();
		a = axis.x*poly1[0].x+axis.y*poly1[0].y;
		int1.SetBoundsUnsafe( a, a );
		if( n > 1 ) {
			a = axis.x*poly1[1].x+axis.y*poly1[1].y;
			int1.SetUUnsafe( a >= int1.L() ? a : int1.L() );
			int1.SetLUnsafe( a < int1.L() ? a : int1.L() );
			for( i = 2; i < n; i++ ) {
				a = axis.x*poly1[i].x+axis.y*poly1[i].y;
				if( a < int1.L() )
					int1.SetLUnsafe( a );
				else if( a > int1.U() )
					int1.SetUUnsafe( a );
			}
		}

		// project poly2's vertices on normal and store interval of values
		a = axis.x*poly2[0].x+axis.y*poly2[0].y;
		int2.SetBoundsUnsafe( a, a );
		if( m > 1 ) {
			a = axis.x*poly2[1].x+axis.y*poly2[1].y;
			int2.SetUUnsafe( a >= int2.L() ? a : int2.L() );
			int2.SetLUnsafe( a < int2.L() ? a : int2.L() );
			for( i = 2; i < m; i++ ) {
				a = axis.x*poly2[i].x+axis.y*poly2[i].y;
				if( a < int2.L() )
					int2.SetLUnsafe( a );
				else if( a > int2.U() )
					int2.SetUUnsafe( a );
			}
		}
		return int1.Intersects( int2 );
	}

	/**
	 * This helper is used in "Crossing"-method. It is used to detect
	 * the crossing-point associated with given bridge.
	 * The bridge is given by vertex index i of n-sided polygon p1 and
	 * vertex index j of m-sided polygon p2.
	 * The indices s (mod n) and t (mod n) of the two polygon edges (s (mod n),s+1 (mod n)),
	 * (t-1 (mod m),t (mod m)) which cross
	 * are returned.
	 * It is assumed that the given polygons intersect.
	 * @param fpMath
	 * @param p1
	 * @param i
	 * @param p2
	 * @param j
	 * @return
	 */
	private static Tuple2<Integer,Integer> StepDown( Point2df[] p1, int i, Point2df[] p2, int j ) {
		int n = p1.length;
		int m = p2.length;

		boolean finished; // found crossing?
		int s = i; // resulting indices s,t
		int t = j;
		int runs; // helper to prevent from hanging
		int sp1_n = (s+1)%n;
		int tm1_m = CircleMod( t-1, m );
		do {
			finished = true;
			runs = 0;
			while( runs <= m && Point2dOps.MakeLeftTurn( p1[s], p1[sp1_n], p2[tm1_m] ) ) {
				t = CircleMod( t-1, m );
				tm1_m = CircleMod( t-1, m );
				finished = false;
				runs++;
			}
			if( runs > m ) {
				break;
			}
			runs = 0;
			while( runs <= n && Point2dOps.MakeRightTurn( p2[t], p2[tm1_m], p1[sp1_n] ) ) {
				s = (s+1)%n;
				sp1_n = (s+1)%n;
				finished = false;
				runs++;
			}
			if( runs > n ) {
				break;
			}
		} while( !finished );
		return new Tuple2<Integer, Integer>( s, t );
	}
}
